
//package java_cup;

//import java.util.Dictionary;
//import java.util.IEnumerator;



using System.Collections;
using System.Text;

/**
 * This class represents a set of LALR ItemSet. For purposes of building these
 * sets, ItemSet are considered unique only if they have unique cores (i.item.,
 * ignoring differences in their lookahead sets).
 * <p>
 *
 * This class provides fairly conventional set oriented operations (union,
 * sub/base-set tests, etc.), as well as an LALR "closure" operation (see
 * compute_closure()).
 *
 * @see java_cup.lalr_item
 * @see java_cup.LALRState
 * @version last updated: 3/6/96
 * @author Scott Hudson
 */
public class LALRItemSet : IEnumerable<LALRItem> {

    /*-----------------------------------------------------------*/
    /*--- Constructor(s) ----------------------------------------*/
    /*-----------------------------------------------------------*/

    /** Constructor for an empty set. */
    public LALRItemSet() { }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /**
     * Constructor for cloning from another set.
     * 
     * @param other indicates set we should copy from.
     */
    public LALRItemSet(LALRItemSet other) /*throws internal_error*/ {
        notNull(other);
        _item2item = new(other._item2item);
    }

    /*-----------------------------------------------------------*/
    /*--- (Access to) Instance Variables ------------------------*/
    /*-----------------------------------------------------------*/

    /**
     * A hash table to implement the set. We store the ItemSet using themselves as
     * keys.
     */
    public Dictionary<LALRItem, LALRItem> _item2item = new(11);

    /** Access to AllVns elements of the set. */
    /*@Override*/
    public IEnumerator<LALRItem> GetEnumerator() {
        return _item2item.Values.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return _item2item.Values.GetEnumerator();
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /** Cached hashcode for this set. */
    public int? hashcode_cache = null;

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /** Size of the set */
    public int Count => _item2item.Count;

    /*-----------------------------------------------------------*/
    /*--- Set Operation Methods ---------------------------------*/
    /*-----------------------------------------------------------*/

    /**
     * Does the set contain a particular item?
     * 
     * @param item the item in question.
     */
    public bool contains(LALRItem itm) {
        return _item2item.ContainsKey(itm);
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /**
     * Return the item in the set matching a particular item (or null if not found)
     * 
     * @param item the item we are looking for.
     */
    public LALRItem Find(LALRItem item) {
        return _item2item[item];
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /**
     * Is this set an (improper) subset of another?
     * 
     * @param other the other set in question.
     */
    public bool isSubsetOf(LALRItemSet other) /*throws internal_error*/ {
        notNull(other);
        /* walk down our set and make sure every element is in the other */
        foreach (LALRItem e in this)
            if (!other.contains(e))
                return false;
        /* they were AllVns there */
        return true;
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /**
     * Is this set an (improper) superset of another?
     * 
     * @param other the other set in question.
     */
    public bool isSupersetOf(LALRItemSet other) /*throws internal_error*/ {
        notNull(other);
        return other.isSubsetOf(this);
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /**
     * Add a singleton item, merging lookahead sets if the item is already part of
     * the set. returns the element of the set that was added or merged into.
     * 
     * @param item the item being added.
     */
    public LALRItem AddMerge(LALRItem item) /*throws internal_error*/ {
        LALRItem other;

        notNull(item);

        /* see if an item with a matching core is already there */
        other = _item2item[item];

        /* if so, merge this lookahead into the original and leave it */
        if (other != null) {
            other.LookAheads.AddRange(item.LookAheads);
            return other;
        }
        /* otherwise we just go in the set */
        else {
            /* invalidate cached hashcode */
            hashcode_cache = null;
            _item2item.Add(item, item);
            return item;
        }
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /**
     * Remove a single item if it is in the set.
     * 
     * @param item the item to remove.
     */
    public void remove(LALRItem item) /*throws internal_error*/ {
        notNull(item);

        /* invalidate cached hashcode */
        hashcode_cache = null;

        /* remove it from hash table implementing set */
        _item2item.Remove(item);
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /**
     * Add a complete set, merging lookaheads where ItemSet are already in the set
     * 
     * @param other the set to be added.
     */
    public void add(LALRItemSet other) /*throws internal_error*/ {
        notNull(other);

        /* walk down the other set and do the adds individually */
        foreach (LALRItem e in other)
            AddMerge(e);
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /**
     * Remove (set subtract) a complete set.
     * 
     * @param other the set to remove.
     */
    public void remove(LALRItemSet other) /*throws internal_error*/ {
        notNull(other);

        /* walk down the other set and do the removes individually */
        foreach (LALRItem item in other) { remove(item); }
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /** Remove and return one item from the set (done in hash order). */
    public LALRItem? getOne() /*throws internal_error*/ {
        if (_item2item.Values.Count == 0)
            return null;
        //var result = GetEnumerator().Current;//.next();
        var result = _item2item.Values.First();
        remove(result);
        return result;
    }

    /*-----------------------------------------------------------*/
    /*--- General Methods ---------------------------------------*/
    /*-----------------------------------------------------------*/

    /**
     * Helper function for null test. Throws an interal_error exception if its
     * parameter is null.
     * 
     * @param obj the object we are testing.
     */
    public void notNull(Object obj) /*throws internal_error*/ {
        if (obj == null)
            throw new InternalError("Null object used in set operation");
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /**
     * Compute the closure of the set using the LALR closure rules. Basically for
     * every item of the form:
     * 
     * <pre>
     *    [L ::= a *N alpha, l]
     * </pre>
     * 
     * (where N is a a non terminal and alpha is a string of EmitSymbols) make sure
     * there are also ItemSet of the form:
     * 
     * <pre>
     *    [N ::= *beta, first(alpha l)]
     * </pre>
     * 
     * corresponding to each production of N. Items with identical cores but
     * differing lookahead sets are merged by creating a new item with the same core
     * and the union of the lookahead sets (the LA in LALR stands for "lookahead
     * merged" and this is where the merger is). This routine assumes that
     * nullable and first sets have been computed for AllVns AllProdctions before it
     * is called.
     */
    public void computeClosure() /*throws internal_error*/ {
        /* invalidate cached hashcode */
        hashcode_cache = null;

        /* each current element needs to be considered */
        var consider = new LALRItemSet(this);

        /* repeat this until there is nothing else to consider */
        while (consider.Count > 0) {
            /* get one item to consider */
            var item = consider.getOne(); if (item == null) { break; }

            /* do we have a dot before a non terminal */
            var Vn = item.VnAfterDot(); if (Vn == null) { continue; }

            /* create the lookahead set based on Vn */
            var new_lookaheads = item.calcLookahead(item.LookAheads);

            /* are we going to need to propagate our lookahead to new item */
            var need_prop = item.LookaheadVisible();

            /* create ItemSet for each production of that non term */
            foreach (var prod in Vn.AllProdctions()) {

                /* create new item with dot at start and that lookahead */
                var newItem = new LALRItem(prod, dotPosition: 0, new VtSet(new_lookaheads));

                /* TryAdd/merge item into the set */
                var add_itm = AddMerge(newItem);
                /* if propagation is needed link to that item */
                if (need_prop) { item.AddPropagate(add_itm); }

                /* was this was a new item */
                if (add_itm == newItem) {
                    /* that may need further closure, consider it also */
                    consider.AddMerge(newItem);
                }
            }
        }
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /** Equality comparison. */
    public bool equals(LALRItemSet other) {
        if (other == null || other.Count != Count)
            return false;

        /* once we know they are the same Count, then improper subset does test */
        try {
            return isSubsetOf(other);
        }
        catch (InternalError e) {
            /* can't throw error from here (because superclass doesn't) so crash */
            e.crash();
            return false;
        }

    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /** Generic equality comparison. */
    /*@Override*/
    public override bool Equals(Object? other) {
        if (!(other is LALRItemSet))
            return false;
        else
            return equals((LALRItemSet)other);
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /** Return hash code. */
    /*@Override*/
    public override int GetHashCode() {
        int result = 0;

        /* only compute a new one if we don't have it cached */
        if (hashcode_cache == null) {
            /* hash together codes from at most first 5 elements */
            // CSA fix! we'd *like* to hash just a few elements, but
            // that means equal sets will have inequal hashcodes, which
            // we're not allowed (by contract) to do. So hash them AllVns.
            foreach (var e in this)
                result ^= e.GetHashCode();

            hashcode_cache = result;
        }

        return hashcode_cache.Value;
    }

    /* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

    /** Convert to string. */
    /*@Override*/
    public override string ToString() {
        var result = new StringBuilder();

        result.Append("{\n");
        foreach (var e in this)
            result.Append("  " + e + "\n");

        result.Append("}");
        return result.ToString();
    }

    /*-----------------------------------------------------------*/
}
